package com.example.question.dp.dp4;

/**
 * @Date 2023-07-28
 * @Author Jonathan
 * 解码方法
 * @link {<a href="https://leetcode.cn/problems/decode-ways/">...</a>}
 */
public class Code03_91 {
    public static void main(String[] args) {
        Code03_91 code = new Code03_91();
        System.out.println("code.numDecodings(\"12\") = " + code.numDecodings("12"));
        System.out.println("code.numDecodings(\"226\") = " + code.numDecodings("226"));
        System.out.println("code.numDecodings(\"06\") = " + code.numDecodings("06"));
    }

    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        return dfs(chars, 0, new Integer[s.length() + 1]);
    }

    /**
     * 使用数组的效率高很多
     */
    private int dfs(char[] chars, int index, Integer[] memo) {
        if (index == chars.length) {
            return 1;
        }

        if (memo[index] != null) {
            return memo[index];
        }

        int res = 0;
        // 截取一位
        if ((chars[index] - 48) > 0) {
            res += dfs(chars, index + 1, memo);
        }
        if (index + 2 <= chars.length) {
            int num2 = (chars[index] - 48) * 10 + (chars[index + 1] - 48);
            if (num2 >= 10 && num2 <= 26) {
                res += dfs(chars, index + 2, memo);
            }
        }
        memo[index] = res;
        return memo[index];
    }


    private int dfs(String s, int index, Integer[] memo) {
        if (index == s.length()) {
            return 1;
        }

        if (memo[index] != null) {
            return memo[index];
        }

        int res = 0;
        // 截取一位


        String str1 = s.substring(index, index + 1);
        if (Integer.parseInt(str1) > 0) {
            res += dfs(s, index + 1, memo);
        }

        if (index + 2 <= s.length()) {
            String str2 = s.substring(index, index + 2);
            int num2 = Integer.parseInt(str2);
            if (num2 >= 10 && num2 <= 26) {
                res += dfs(s, index + 2, memo);
            }
        }
        memo[index] = res;
        return memo[index];
    }

}
